package bintree.newcoder;

public class JZ36平衡二叉树转换为双向链表 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null){
            return null;
        }
        // 1.先将左子树转为排序后的双向链表
        TreeNode leftHead= Convert(pRootOfTree.left);
        // 2.找到l1链表的尾结点和当前的树根拼接
        TreeNode leftTail = leftHead;
        while (leftTail!=null&&leftTail.right!=null){
            leftTail=leftTail.right;
        }
        // leftTail走到了l1的尾结点
        // 这里判空的原因左子树就是个空树
        if (leftTail!=null){
            // 进行拼接
            leftTail.right=pRootOfTree;
            pRootOfTree.left=leftTail;
        }
        // 此时l1和root连接起来了
        // 3.再将右子树也转为双向链表
        TreeNode rightHead=Convert(pRootOfTree.right);
        // 将l2的头结点和root拼接
        if (rightHead!=null){
            pRootOfTree.right=rightHead;
            rightHead.left=pRootOfTree;
        }
        // 返回链表的开始节点。
        return leftHead==null?pRootOfTree:leftHead;
    }
}
